import java.util.HashMap;
import java.util.Map;

/**
 * 剑指 Offer 35. 复杂链表的复制
 * https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof/
 */
public class Solutions_Offer_45 {
    public static void main(String[] args) {
        Node_O45 node0 = new Node_O45(7);
        Node_O45 node1 = new Node_O45(13);
        Node_O45 node2 = new Node_O45(11);
        Node_O45 node3 = new Node_O45(10);
        Node_O45 node4 = new Node_O45(1);

        node0.next = node1;
        node1.random = node0;
        node1.next = node2;
        node2.next = node3;
        node2.random = node4;
        node3.next = node4;
        node3.random = node2;
        node4.random = node0;  // input:{{7, null}, {13, 0}, {11, 4}, {10, 2}, {1, 0}}
                               // ouput:{{7, null}, {13, 0}, {11, 4}, {10, 2}, {1, 0}}

        Node_O45 result = copyRandomList(node0);
        System.out.println(result);
    }

    public static Node_O45 copyRandomList(Node_O45 head) {
        if (head == null) {
            return null;
        }
        // 键为 head 中的结点，值为其拷贝结点
        Map<Node_O45, Node_O45> map = new HashMap<>();
        Node_O45 cur = head;
        while (cur != null) {
            // 拷贝每个结点（next, random 关系后续处理），保持结点值一致，同时将原结束与拷贝结点映射到 map 中
            map.put(cur, new Node_O45(cur.val));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            // 获取到 cur 的克隆结点
            Node_O45 cloneNode = map.get(cur);
            // 让克隆结点保持与原结点相同的 next 和 random
            // 只不过 next 与 random 不能是 head 中的结点，也应该是其对应结点的拷贝结点
            cloneNode.next = map.get(cur.next);
            cloneNode.random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

class Node_O45 {
    int val;
    Node_O45 next;
    Node_O45 random;

    public Node_O45(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
